#include <math.h>
#include <stdlib.h>
#include <unistd.h>

#include <iostream>

#ifdef GMPI
#include <mpi.h>
#endif

#include "gsolverBBPv3NoWait.h"
#include "glowerbound.h"

/**
 * A BBP solver : starts with jobs with last due dates
 *
 * Dans cette version 3 de la BBP, on demarre avec les jobs reordonnes dans le sens des dates dues croissantes. Mais
 * contrairement a l'exploration brutale de la version 2, cette fois on ne considere pas n'importe quel numero de batch.
 * Pour chaque job, on choisit de le rajouter soit dans un batch deja existant dont la capacite residuel est suffisante
 * pour stocker le nouveau job, soit dans un nouveau batch.
 *
 * Le nouveau batch est ordonnance avant les autres batchs deja crees.
 *
 * ATTENTION : Pour que cette solution soit optimale, sachant que l'on
 * part d'un probleme pour lequel les jobs sont classes par date due croissante, il est egalement necessaire que le cout de stockage
 * de tous les jobs soient identiques. Dans le cas contraire, la solution ainsi construite n'est plus certaine d'etre optimale.
 */
GSolverBBPv3NoWait::GSolverBBPv3NoWait(GSupplyLinkProblem& pb, int node_, int p_):GSolverBBPv3(pb,node_,p_) {
  setPeriodMPITestSlave(DEFAULT_PERIOD_MPI_TEST_SLAVE) ;
  setPeriodMPITestMaster(DEFAULT_PERIOD_MPI_TEST_MASTER) ;
  int lvlfordispatch = problem.getNP()-MIN_LEVEL_FOR_DISPATCHING ;
  if (lvlfordispatch<0) lvlfordispatch = 0 ;
  setDepthLevelForDispatching(lvlfordispatch) ;

  setOnlyNewBatchFirst(0) ;
  nbrCut = 0 ;
  nbrTreeNodes = 0 ;
  lowerBound = new GLowerBoundV0(&problem) ;

}


GSolverBBPv3NoWait::~GSolverBBPv3NoWait() {
  if (lowerBound) delete lowerBound ;
}


void GSolverBBPv3NoWait::setLowerBoundLevel(int l) { 
  lowerBoundLevel = l ; 
  if (lowerBoundLevel>0) {
    if (lowerBound) delete lowerBound ;
    switch (lowerBoundLevel) {
    case 1 : lowerBound = new GLowerBoundV1(&problem) ; break ;
    }
  }
}

/**
 * Interval of the search tree to dispatch the work to the slaves
 * If the task are too small, the time to communicate will be very high
 * if the task are too important, some nodes could starve and will have nothing to do.
 * 
 * As the search is done from the last job n back to the first one, these values should
 * be rather close than 100% than 0% in order to to schedule few big tasks rather than 
 * a lot of small tasks. 
 */
void GSolverBBPv3NoWait::setDepthLevelForDispatching (int d) {
  depthLevelForDispatching = d ;
  if (!node) cout << "depthLevelForDispatching="<<depthLevelForDispatching<<"/"<<problem.getNP()<<endl ;
}


/**
 *
 */
void GSolverBBPv3NoWait::setPeriodMPITestSlave (int sec) {
  alarmMPITestSlave.setAlarmDuration(sec) ;
  if (!node) cout << "period_MPI_Test_Slave="<<sec<<"secs"<<endl ;
}


/**
 *
 */
void GSolverBBPv3NoWait::setPeriodMPITestMaster (int sec) {
  alarmMPITestMaster.setAlarmDuration(sec) ;
  if (!node) cout << "period_MPI_Test_Master="<<sec<<"secs"<<endl ;
}


/**
 * @param periods : period in ms of the MPI communication test for the slave nodes
 * @param periodm : period in ms of the MPI communication test for the master node
 */
void GSolverBBPv3NoWait::setPeriodMPITestParameter (int periods, int periodm) {
  if (periods!=alarmMPITestSlave.getAlarmDuration()) setPeriodMPITestSlave(periods) ;
  if (periodm!=alarmMPITestMaster.getAlarmDuration()) setPeriodMPITestMaster(periodm) ;
}




/**
 *
 */
void GSolverBBPv3NoWait::solveInit() {
  // If all the sizes are greater than capacity/2, no need to insert the batches at all the position
  if (!onlyNewBatchFirst) {
    double capa_2 = problem.getTransporter(0).getCapacity()/2.0 ;
    int smallbatch=0 ;
    for (int i=0;i<problem.getNP();++i) {
      if (problem.getJobSize(i)<=capa_2) smallbatch = 1 ;
    }
    if (!smallbatch) {
      onlyNewBatchFirst = 1 ;
      if (!node) {
	coutline() ;
	cout << "GSolverBBPv3NoWait::solveInit() : " << endl ;
	cout << "  special case, all the batch sizes are greater than the capacity / 2," << endl ;
	cout << "  no need to insert new batches at all position. onlyNewBatchFirst = " << onlyNewBatchFirst << endl ;
      }

    }
  }

  assert (lowerBound) ;

}


/**
 *
 */
void GSolverBBPv3NoWait::solveEnd() {
  GSolverBBPv3::solveEnd() ;
  double cutEff = 0.0 ;
  if (nbrTreeNodes) cutEff = 100.0*nbrCut/nbrTreeNodes ;
  cout << "Node " << node << " : Cut Efficiency = " << cutEff << "% (nbrcCut=" << nbrCut << " / nbrTreeNodes=" << nbrTreeNodes << ")" << endl ;
  cout << endl ;
}





/**
 * DepthFirstSearch (BBP) with a single process
 */
void GSolverBBPv3NoWait::depthFirstSearch(const searchnode& treenode) {
  double result ;
  int workHasBeenDispatched = 0 ;

  nbrTreeNodes++ ;

#ifdef GMPI
  testForMPIComm() ;
#endif

  // Evaluation of the newly built solution
  if (treenode.job<0) {
    GSupplyLinkSolution newsol (treenode.sol) ;
    //newsol.setStartEnd(0,this->problem.getNP()-1) ;
    //newsol.compacteBatches() ;
    double eval = newsol.evaluate() ;
    if (bestSolutionDueDateOrdered.getEvaluation()<0 || eval<bestSolutionDueDateOrdered.getEvaluation()) {
      bestSolutionDueDateOrdered = newsol ;
      sendMPICommForBestSolution(eval) ;


      coutline() ;
      if (!node) cout << "Master " ;
      else cout << "Slave node" << node ;
      cout << " : New best solution : eval="<< bestSolutionDueDateOrdered.getEvaluation() ;
      cout << "(transp=" << bestSolutionDueDateOrdered.getEvaluationTransporter() ;
      cout << " ; stock=" << bestSolutionDueDateOrdered.getEvaluationCustomer() << ") : " ;
      double perccut = 100.0*(double)nbrCut/(double)nbrTreeNodes ;
      cout << "%cut=" << perccut << "%" << endl ;
      cout << endl ;

    }
    return ;
  }

  // Add job in a batch, if batchjob==-1 => create a new batch before
  // for (int batchPotentialIndice=treenode.nbrbatch-1;batchPotentialIndice>=-1;batchPotentialIndice--) {
  int minBatchPotentialIndice = -treenode.nbrbatch-1 ;
  if (onlyNewBatchFirst) 
    minBatchPotentialIndice = -1 ;

  // cout << "=====================================================" << endl ;
  // cout << "minBatchPotentialIndice = " << minBatchPotentialIndice << endl ;
  // cout << "treenode = " << treenode << endl ;

  for (int batchPotentialIndice=treenode.nbrbatch-1;batchPotentialIndice>=minBatchPotentialIndice;batchPotentialIndice--) {

    double jobsize = this->problem.getJobSize(treenode.job) ;
    int batchRealIndice=-1 ;
    int incnbrbatch = -1 ;


    // Job is added to an existing batch
    if (batchPotentialIndice>=0 && treenode.tabBatchRemainingCapacity[batchPotentialIndice]>=jobsize) {
      batchRealIndice= batchPotentialIndice ;
      incnbrbatch = 0 ;
    }

    // Creation of a new batch
    if (batchPotentialIndice<0) {
      batchRealIndice=-batchPotentialIndice-1 ;
      incnbrbatch = 1 ;
    }

    // Transformation of the solution
    if (incnbrbatch>=0) {
      searchnode treenodechild ;
      treenodechild.nbrbatch = treenode.nbrbatch+incnbrbatch ;
      treenodechild.job = treenode.job-1 ;
      treenodechild.sol = treenode.sol;
      treenodechild.tabBatchRemainingCapacity = treenode.tabBatchRemainingCapacity ;

      if (incnbrbatch>0) {
//	cout << "inserting at " << batchRealIndice << endl ;
	// treenodechild.tabBatchRemainingCapacity.insert(treenodechild.tabBatchRemainingCapacity.begin(),this->problem.getTransporter(0).getCapacity()) ;
        treenodechild.tabBatchRemainingCapacity.insert(treenodechild.tabBatchRemainingCapacity.begin()+batchRealIndice,this->problem.getTransporter(0).getCapacity()) ;
        // The batch indices of previously placed jobs should be increased
        for (int job2=treenode.job+1;job2<problem.getNP();job2++) {
	  int bi = treenodechild.sol.getBatchIndice(job2) ;
	  if (bi>batchRealIndice){
//	    cout << "translating job " << job2 << " from batch " << treenodechild.sol.getBatchIndice(job2) << " to batch " << 1+treenodechild.sol.getBatchIndice(job2) << endl ;
	    treenodechild.sol.setBatchIndice(job2,1+bi) ;
	  }
        }
      }
      treenodechild.tabBatchRemainingCapacity[batchRealIndice] -= jobsize ;
      treenodechild.sol.setBatchIndice(treenode.job, batchRealIndice+1) ;
      treenodechild.sol.setDeliveryCompletionTime(treenode.job, (double)batchRealIndice+1) ;
      treenodechild.sol.setNbrBatch(treenode.nbrbatch+incnbrbatch) ;

      double lowerbound = lowerBound->evaluate(treenodechild.sol, treenode.job);
      assert (lowerbound>=0) ;

      if (lowerbound<bestSolutionDueDateOrdered.getEvaluation()) {
#ifdef GMPI
	if (pushWork(treenodechild)==WORK_NOT_DISPATCHED)
#endif
          depthFirstSearch(treenodechild) ;
      }
      else {
	if (treenodechild.job>=0) {
	  nbrCut++ ;
	  nbrTreeNodes++ ;
	}
      }
      
    }
  }
}

